/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#ifndef PartialOrder_HEV9XC6X

#define PartialOrder_HEV9XC6X

#include <vector>
#include <set>

#include "Interval.h"
#include "Matrix.h"

class PartialOrder
{
    public:

        PartialOrder ( Matrix *m );
        PartialOrder ( Matrix m );

        /**
         * @brief reinit PartialOrder with epsilon
         *
         * @param epsilon epsilon
         */
        void reinit( double epsilon, bool fast );

        void setEpsilon( double epsilon )
        {
            _dEpsilon = epsilon;
        }

        /**
         * @brief Update the canonical partial order using the rules (B1)-(B4) and (PO1)-(PO6) for all interval
         * if fast equal false, the algorithm may find a little better solution, but it's much slower.
         * How ever it depends of the dissimilarity matrix
         */
        void update(bool allRules=false, bool fast=false);

        /**
         * @brief set p <= q for tow arbitrary elements p, q in Matrix.
         */
        void setOrderForTwoArbitraryElements(bool forceSetSecondeElements);

        void setOrientation(unsigned int a, unsigned int b);

        /**
         * @brief Adds an element to B
         */ 
        void addElementToB(Interval *interval, int u);

        bool topologicalSorting();

        virtual ~PartialOrder ();

        std::vector< std::set<unsigned int> >& getGraph();
        void setConstructBeetweness(bool val);
        bool constructBeetweness();
        Matrix *getMatrix();

        void afficher()
        {
            std::cerr << "Partial Order Graph : " << std::endl;
            for (unsigned int i = 0; i < _vsGraphe.size(); i++)
            {
                std::cerr << i << " : ";
                for (std::set<unsigned int>::iterator it = _vsGraphe[i].begin(); it != _vsGraphe[i].end(); ++it)
                    std::cerr << *it << " ";
                std::cerr << std::endl;
            }
        }

    private:

        PartialOrder( const PartialOrder & )
        {}
        void init();

        Interval* getInterval(unsigned i, unsigned j);

        /**
         * @brief update the canonical partial order using the rules (B1)-(B4) and (PO1)-(PO6) in interval "interval"
         *
         * @param interval interval using for apply rules
         */
        void update( std::pair<unsigned int, unsigned int> p, bool allRules, bool fast );

        void PO1( unsigned int x, unsigned int y );
        void PO1_fast( unsigned int x, unsigned int y );
        void PO2( unsigned int x, unsigned int y );
        void PO3_4_5_6( unsigned int x, unsigned int y );

        bool B1( unsigned int u, Interval* interval );
        bool B2( unsigned int u, Interval* interval );
        bool B3( unsigned int u, Interval* interval );
        bool B4( unsigned int u, Interval* interval );

        Matrix _pSubMatrix;
        Matrix* _pMatrix;
        double  _dEpsilon;


        /**
         * @brief Graph of Partial Order
         */
        std::vector< std::set<unsigned int> > _vsGraphe;


        /**
         * @brief like _vsGraphe with inverse arc
         */
        std::vector< std::set<unsigned int> > _vsNoGraphe;


        /** (owner of Interval)
         * @brief Get interval by min point and max point
         */
        std::vector< std::vector<Interval*> > _vvpInterval;

        /**
         * @brief get all intergal for 1 element
         */
        std::vector< std::set<Interval*> > _vspInterval;



        //std::set<Interval*> _sToUpdate;
        std::set< std::pair<unsigned int, unsigned int> > _spToUpdate;

        std::vector<unsigned int> _vTopologicalSorting;

        bool _constructBeetweness;


        /**
         * @brief show partial order (exemple for cout)
         *
         * @param os output stream
         * @param o partial order
         *
         * @return output stream
         */
        friend std::ostream& operator << (std::ostream& os, const PartialOrder& o);
};

/**
 * Show Partial Order
 */
std::ostream& operator << (std::ostream& os, const PartialOrder& o);

#endif /* end of include guard: PartialOrder_HEV9XC6X */

